package study.sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        System.out.println("排序前：" + Arrays.toString(arr));
        shellSort4(arr);

    }

    /**
     * 推导过程（交换法）
     * @param arr
     */
    public static void shellSort2(int[] arr) {
        //arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0}
        int temp = 0;
        //第1轮 步长 = 5
        //分组：第1轮分5组（10 / 2 = 5）
        for (int i = 5; i < arr.length; i++) {
            for (int j = i - 5; j >= 0; j -= 5) {
                //如果当前值 大于 加上步长后的那个位置的值，则交换位置
                if (arr[j] > arr[j+5]){
                    //交换位置
                    temp = arr[j];
                    arr[j] = arr[j+5];
                    arr[j+5] = temp;
                }
            }
        }

        System.out.println("第1轮排序后的结果：" + Arrays.toString(arr));

        //[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
        //第2轮 步长 = 2
        //分组：第2轮分2组(5 / 2 = 2)
        for (int i = 2; i < arr.length; i++) {
            for (int j = i - 2; j >= 0; j -= 2) {
                //如果当前值 大于 加上步长后的那个位置的值，则交换位置
                if (arr[j] > arr[j+2]){
                    //交换位置
                    temp = arr[j];
                    arr[j] = arr[j+2];
                    arr[j+2] = temp;
                }
            }
        }

        System.out.println("第2轮排序后的结果：" + Arrays.toString(arr));



        //[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
        //第3轮 步长 = 1
        //分组：第2轮分2组(2 / 2 = 1)
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0; j -= 1) {
                //如果当前值 大于 加上步长后的那个位置的值，则交换位置
                if (arr[j] > arr[j+1]){
                    //交换位置
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }

        System.out.println("第3轮排序后的结果：" + Arrays.toString(arr));

    }

    
    /**
     * 整理代码（交换法）
     * @param arr
     */
    public static void shellSort3(int[] arr) {
        //arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0}
        int temp = 0;
        int count = 0;
        for (int step = arr.length / 2; step > 0; step /= 2) {
            for (int i = step; i < arr.length; i++) {
                for (int j = i - step; j >= 0; j -= step) {
                    //如果当前值 大于 加上步长后的那个位置的值，则交换位置
                    if (arr[j] > arr[j+step]){
                        //交换位置
                        temp = arr[j];
                        arr[j] = arr[j+step];
                        arr[j+step] = temp;
                    }
                }
            }

            System.out.println("第" + ( ++count )+ "轮排序后的结果：" + Arrays.toString(arr));
        }
    }


    /**
     * 整理代码（移位法）
     * @param arr
     */
    public static void shellSort4(int[] arr) {
        //arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0}
        int count = 0;
        for (int step = arr.length / 2; step > 0; step /= 2) {
            for (int i = step; i < arr.length; i++) {
                //第1轮 tempIndex = i = step = 5
                int tempIndex = i;
                //第1轮 tempValue = arr[tempIndex] = arr[5] = 3
                int tempValue = arr[tempIndex];
                //如果下标为元素的那个元素 小于 下标减步长的那个元素
                /**
                 * 第1轮
                 * 即
                 * arr[i] = arr[5] = 3，
                 * arr[i - step] = arr[5-5] = arr[0] = 8
                 * 3 < 8，需要找位置
                 */
                if (arr[i] < arr[i - step]){
                    /**
                     * 条件1：tempIndex - step >= 0，保证数组不会越界
                     * 条件2：tempValue < arr[tempIndex - step]，说明还要找位置
                     */
                    while (tempIndex - step >= 0 && tempValue < arr[tempIndex - step]){
                        //移动
                        //arr[5] = arr[0]
                        arr[tempIndex] = arr[tempIndex - step];
                        tempIndex -= step;
                    }
                    //退出循环后，找到位置
                    arr[tempIndex] = tempValue;
                }

            }

            System.out.println("第" + ( ++count )+ "轮排序后的结果：" + Arrays.toString(arr));
        }
    }

    public static void shellSort(int[] arr) {
        //arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        //分5组 {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        //(8,3) (9,5) (1,4) (7,6) (2,0)
        int temp = 0;
        for (int k = 0; k < 10 / 2; k++) {
            if (arr[k] > arr[k+5]){
                temp = arr[k];
                arr[k] = arr[k+5];
                arr[k+5] = temp;
            }
        }
        System.out.println("第1轮排序：" + Arrays.toString(arr));

    }


}
